package me.sealer.algorithm.sort;

/**
 * Created by sealer on 17/03/05.
 */
public class Merge2 {


    public static void sort(int[] nums) {
        sort(nums, 0, nums.length - 1);
    }

    /**
     * 递归方式
     *
     * @param nums
     * @param low
     * @param high
     */
    public static void sort(int[] nums, int low, int high) {
        int mid = (low + high) / 2;
        if (low < high) {
            sort(nums, low, mid);
            sort(nums, mid + 1, high);
            merge(nums, low, mid, high);
        }
    }

    private static void merge(int[] nums, int low, int mid, int high) {
        int[] temp = new int[high - low + 1];
        int i = low;
        int j = mid + 1;
        int k = 0;

        while (i <= mid && j <= high) {
            if (nums[i] < nums[j]) {
                temp[k++] = nums[i++];
            } else {
                temp[k++] = nums[j++];
            }
        }

        while (i <= mid) {
            temp[k++] = nums[i++];
        }

        while (j <= high) {
            temp[k++] = nums[j++];
        }

        for (int l = 0, m = low; m <= high; ) {
            nums[m++] = temp[l++];
        }
    }
}
